# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        errorNode = []
        def nextNode(nowNode, lastTmp):
            if nowNode is None:
                return lastTmp
            if nowNode.left:
                lastTmp = nextNode(nowNode.left, lastTmp)
            if len(errorNode) >= 3:
                return lastTmp
            if lastTmp is None:
                lastTmp = nowNode
            else:
                print(nowNode.val)
                if lastTmp.val > nowNode.val:
                    errorNode.append(lastTmp)
                    errorNode.append(nowNode)
                lastTmp = nowNode
            if len(errorNode) >= 3:
                return lastTmp
            lastTmp = nextNode(nowNode.right, lastTmp)
            return lastTmp
        nextNode(root, None)
        print(errorNode)
        errorNode[0].val,errorNode[-1].val = errorNode[-1].val,errorNode[0].val
        return

# if __name__ == '__main__':
#     so = Solution()
#     # s1 = "aabcc"
#     # s2 = "dbbca"
#     # s3 = "aadbbcbcac"
#     s1 = "aabcc"
#     s2 = "dbbca"
#     s3 = "aadbbbaccc"
#     r = so.isInterleave(s1, s2 ,s3)
#     print(r)
